/*
https://leetcode-cn.com/problems/minimize-malware-spread-ii/solution/jin-liang-jian-shao-e-yi-ruan-jian-de-chuan-bo-ii-/
 */
import java.util.*;

public class Solution928 {

    static class BingChaJi{
        int[] b;
        int[] size;
        int res;

        public BingChaJi(int n){
            b=new int[n];
            size=new int[n];
            for (int i=0;i<n;i++){
                b[i]=i;
                size[i]=1;
            }
            res=n;
        }

        public int find(int t){
            return b[t]==t?t:(b[t]=find(b[t]));
        }

        public void union(int x,int y){
            int p=find(x);
            int q=find(y);
            if (p!=q){
                b[p]=q;
                size[q]+=size[p];
            }
            res--;
        }
    }

    public int minMalwareSpread(int[][] graph, int[] initial) {
        Set<Integer> set=new HashSet<>();
        for (int i : initial) {
            set.add(i);
        }
        BingChaJi bingChaJi=new BingChaJi(graph.length);
        for (int i=0;i<graph.length;i++){
            for (int j=i+1;j<graph.length;j++){
                if (!set.contains(i) && !set.contains(j) && graph[i][j]==1){
                    bingChaJi.union(i,j);
                }
            }
        }
        Arrays.sort(initial);
        Map<Integer, Set<Integer>> map=new HashMap<>();
        for (int i:initial){
            for (int j=0;j<graph.length;j++){
                if (!set.contains(j) && graph[i][j]==1){
                    int x=bingChaJi.find(j);
                    map.putIfAbsent(x,new HashSet<>());
                    map.get(x).add(i);
                }
            }
        }
        int[] f=new int[301];
        for (Map.Entry<Integer, Set<Integer>> integerSetEntry : map.entrySet()) {
            if (integerSetEntry.getValue().size()==1){
                List<Integer> list=new ArrayList<>(integerSetEntry.getValue());
                f[list.get(0)]+=bingChaJi.size[integerSetEntry.getKey()];
            }
        }
        int max=0;
        int ans=initial[0];
        for (int i : initial) {
            if (f[i]>max){
                max=f[i];
                ans=i;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution928().minMalwareSpread(new int[][]{{1,0,0,0,0,0,0,0,0},{0,1,0,0,0,0,0,0,1},
                {0,0,1,0,0,0,0,0,0},{0,0,0,1,0,0,0,0,1},{0,0,0,0,1,0,1,1,1},{0,0,0,0,0,1,0,0,1},{0,0,0,0,1,0,1,1,0},
                {0,0,0,0,1,0,1,1,0},{0,1,0,1,1,1,0,0,1}},new int[]{8,4,2,0}));
    }
}
